public class 接雨水 {

    // 求每个位置的最大雨水数
    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) {
            return 0;
        }
        int[] leftdp = new int[n + 1]; // 当前位置左边的最大值
        int[] rightdp = new int[n + 1]; // 当前位置右边的最大值
        for (int i = 1;i <= n;i++) {
            leftdp[i] = Math.max(leftdp[i - 1],height[i - 1]);
        }
        for (int i = n - 1;i >= 0;i--) {
            rightdp[i] = Math.max(rightdp[i + 1],height[i]);
        }
        int ans = 0; // 返回值
        for (int i = 0;i < n;i++) {
            // 每次找到左边包括自己的最大值所以要 i + 1,
            // 找到当前位置右边的最大值然后减去自己的高度
            // 求出每个位置的最大雨水数
            ans += Math.min(leftdp[i + 1],rightdp[i]) - height[i];
        }
        return ans;
    }
}
